/**
 * @param {number[][]} points
 * @return {number}
 */
var minCostConnectPoints = function (points) {
  let n = points.length // 获得这个的长度
  let edges = []
  for (let i = 0; i < n; i++) { // 遍历每一个节点
    for (let j = i + 1; j < n; j++) { // 遍历这个节点后面的每一个节点
      let lx = points[i][0], ly = points[i][1]
      let rx = points[j][0], ry = points[j][1] // 获得这个的左右坐标
      edges.push([i, j, Math.abs(lx - rx) + Math.abs(ly - ry)]) // 生成边数组 i 表示左节点 j表示右节点 ,第三个表示权重
    }
  }
  let uf = new UnionFind(n) // 生成n的并查集
  edges.sort((a, b) => a[2] - b[2]) // 按照权重的节点进行递增排序
  let mst = 0 // 初始化权重
  for (let i = 0; i < edges.length; i++) {
    let from = edges[i][0]
    let to = edges[i][1]
    let cost = edges[i][2]
    if (uf.connected(from, to)) {
      continue
    }
    mst += cost // 加上这个权重
    uf.union(from, to)
  }
  return mst
};
class UnionFind {
  constructor(n) { // n表示图纸节点的个数
    this.count = n // 连通分量的个数
    this.parent = new Array(n) // 储存每个节点的父节点  下标代表节点的编号 值是节点的父节点
    for (let i = 0; i < n; i++) {
      this.parent[i] = i // 初始化每个节点的父节点都是自己本身
    }
  }
  union (p, q) {
    let rootP = this.find(p)
    let rootQ = this.find(q)
    if (rootP === rootQ) {
      return
    }
    this.parent[rootP] = rootQ // 让其中一个指向另一个的父节点
    this.count-- // 连通的分量减一  因为两个合成了一个了
  }
  connected (p, q) {
    let rootP = this.find(p)
    let rootQ = this.find(q)
    return rootQ === rootP // 找到两个的根节点 判断是不是相同
  }
  find (x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }
  getCount () {
    return this.count // 返回连通量的个数
  }
}